package com.xxy.tree;

import java.util.Arrays;

/**
 * @author xxy
 * @create 2021 1 27 11:52
 * 堆排序的基本思想：
 * 1）将待排序序列构造成一个大顶堆
 * 2）此时，整个序列的最大值就是堆顶的根节点
 * 3）将其与末尾元素进行交换，此时末尾就为最大值
 * 4）然后将剩余n-1个元素重新构造成一个堆，这样就会得到n个元素的次小值。如此反复执行，便能得到一个有序序列
 */
public class HeapSort {
    public static void main(String[] args) {
        int arr[] ={4,6,8,5,9};
        heapSort(arr);
    }
    public static void heapSort(int arr[]){
        int temp =0;
        System.out.println("堆排序！！！");
        //1.将无序列构建成一个堆，根据升降序需求选择大顶堆或 小顶堆
        for(int i = arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }
        //2.将堆顶元素与末尾元素交换，将最大元素沉到数组末端
        //3.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整交换步骤，直到序列有序
        for(int j = arr.length-1;j>0;j--){
            temp =arr[j];
            arr[j]=arr[0];
            arr[0]=temp;
            adjustHeap(arr,0,j);
        }
        System.out.println("数组="+ Arrays.toString(arr));
    }

    /**
     *功能：完成将以i对应的非叶子节点的树调整为大顶堆
     * 举例：int arr[] = {4,6,8,5,9}=> i = 1=>adjustHeap=>得到{4，9,8,5,6}
     * 如果再次调用adjustHeap（）出入的是i=0=>得到{4,9,8,5,6}=>{9,6,8,5,4}
     * @param arr 待调整的数组
     * @param i 表示非叶子结点在数组中的索引
     * @param length 表示对多少元素进行调整，length是在逐渐减少
     */
    public static void adjustHeap(int arr[],int i,int length){
        int temp =arr[i];//先取出当前元素的值，保存临时变量
        //开始调整
        //说明
        //1.k=i*2+1 k是i节点的左子节点
        for(int k = i*2+1;k<length;k=k*2+1){
            if(k+1<length&&arr[k]<arr[k+1]){//选择较大的节点
                k++;//k指向右子节点
            }
            if(arr[k]>temp){//如果子节点大于父节点
                arr[i]=arr[k];//把较大的值赋给当前节点
                i=k;//i指向k 循环比较
            }else{
                break;
            }
        }
        //当for循环结束后，我们已经将以i为父节点的树的最大值，放在了最顶（局部）
        arr[i] = temp;//将temp值放到调整后的位置
    }
}
//113